package algorithm.leetcode.I201to400;

import algorithm.leetcode.TreeNode;

/**
 * BST的中序遍历是递增序列
 * 频繁插入和删除用数组维护BST
 */

public class Q230 {

    int res = 0;
    int index = 0;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return res;
    }

    private void inorder(TreeNode node, int k) {
        if (node == null) return;

        inorder(node.left, k);
        if (++index == k) res = node.val;
        inorder(node.right, k);
    }
}
